/**
 * 
 */
package homework5;

import java.util.HashMap;

/**
 * @author Nican
 * Look for the Levenshtein distance between the two strings
 */
public class Levenshtein {
	
	/**
	 * Contain all the cached values on the array
	 */
	HashMap<Vector, Integer> memoization = new HashMap<Vector, Integer>();
	String str1;
	String str2;
	
	public Levenshtein(String str1, String str2) {
		this.str1 = str1;
		this.str2 = str2;
	}
	
	/**
	 * Calculate the last value of the levenshtein
	 * @return
	 */
	public Integer minValue() {
		return LevenshteinValue(this.str1.length(), this.str2.length());
	}
	
	/**
	 * Calculate the lavenshtein value at the given point
	 * @param x the disance of the str1
	 * @param y the distance of the str2
	 * @return Integer containing the disance
	 */
	public Integer LevenshteinValue(int x, int y) {
		
		//Creates a new object that will serve as the key for the hash map
		Vector vector = new Vector(x, y);

		//If a key with similar propreties already exist, return the value that is assigned to it
		if (memoization.containsKey(vector)) {
			return memoization.get(vector);
		}
		
		//Calculate the value at the point
		Integer val = calculateLevenshteinValue(x, y);

		//And store it in the cache
		memoization.put(vector, val);

		return val;

	}

	private Integer calculateLevenshteinValue(int x, int y) {

		if (x == 0)
			return y;
		if (y == 0)
			return x;

		if (str1.charAt(x - 1) == str2.charAt(y - 1))
			return LevenshteinValue(x - 1, y - 1);

		Integer top = LevenshteinValue(x, y - 1);
		Integer left = LevenshteinValue(x - 1, y);
		Integer topLeft = LevenshteinValue(x - 1, y - 1);

		return Math.min(top, Math.min(left, topLeft)) + 1;

	}

}
